package sword_to_1;

import node.TreeNode;

public class LeeCode_26 {
    public static void main(String[] args) {
        System.out.println(isSubStructure(new TreeNode(1, new TreeNode(0, new TreeNode(-4), new TreeNode(-3)), new TreeNode(1)),
                new TreeNode(1, new TreeNode(-4), null)));
    }
    private static boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null){
            return false;
        }
        return dfs(A, B, true);
    }

    private static boolean dfs(TreeNode A, TreeNode B, boolean isRoot) {
        boolean f1 = false, f2 = false, f3 = false;
        if (B == null){
            return true;
        }
        if (A == null){
            return false;
        }
        if (A.val == B.val){
            f1 = dfs(A.left, B.left, false) && dfs(A.right, B.right, false);
        }
        if (isRoot){
            f2 = dfs(A.left, B, isRoot);
            f3 = dfs(A.right, B, isRoot);
        }
        return f1 || f2 || f3;
    }
}
